// This is quick sort algorithm implementation.
#include<stdio.h>

void merge(std::vector<int>& A, std::vector<int>& A_temp, size_t left, size_t mid, size_t right) {
	for (size_t i = left; i <= mid; i++) {
		A_temp[i] = A[i];
	}
	for (size_t j = mid + 1; j <= right; j++) {
		A_temp[j] = A[right + mid + 1 - j];
	}

	size_t i = left, j = right;
	size_t k = left;
	while ( k <= right) {
		if (A_temp[i] < A_temp[j]) {
			A[k] = A_temp[i];
			i++;
		} 
		else {
			A[k] = A_temp[j];
			j--;
		}
		k++;			
	}
}

void mergeSort(std::vector<int>& A, size_t left, size_t right) {
	static std::vector<int> A_temp(A.size());
	if (left >= right)
		return;
	size_t mid = (left + right) / 2;
	mergeSort(A, left, mid);
	mergeSort(A, mid + 1, right);
	merge(A, A_temp, left, mid, right);	
}

void display(std::vector<int>& arr, int n) 
{
	for (int i = 0; i < n; i++)
		printf(" \n%d ", arr[i]);
}

int main() 
{
	int n = 8;
	std::vector<int> arr = { 3, 1, 2, 5, 6, 3, 8, 7 };
	
	// int arr[] = { 1, 2, 3, 7 };
	// int arr[] = { 8, 6, 7};
	mergeSort(arr, 0, n - 1);
	display(arr, n);
}